//思路一：直接二重循环旋转   时间复杂度：O(n*k)
void rotate(int* nums, int numsSize, int k) {
    while(k--){
        int tmp = nums[numsSize - 1];
        for(int i = numsSize - 2; i >= 0; i--){
            nums[i + 1] = nums[i];
        }
        nums[0] = tmp;
    }
}

//思路二：三次逆置    时间复杂度：O(n)
void Reverse(int* nums, int left, int right){
    while(left < right){
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
        left++;
        right--;
    }
}


void rotate(int* nums, int numsSize, int k) {
    if(k >= numsSize){
        k %= numsSize;
    }

    Reverse(nums, numsSize - k, numsSize - 1);
    Reverse(nums, 0, numsSize - k - 1);
    Reverse(nums, 0, numsSize - 1);

}

/*给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。*/